\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand*\HyPL@Entry[1]{}
\citation{KSXZ04,LSOXZ06}
\HyPL@Entry{0<</S/D>>}
\@writefile{toc}{\contentsline {section}{\numberline {I}Introduction}{1}{section.1}}
\newlabel{sec:intro}{{I}{1}{Introduction}{section.1}{}}
\citation{WJ03}
\citation{CHANDRA}
\citation{SKA}
\citation{MFHH05}
\citation{CPB93,KMFB04}
\citation{KBG04}
\citation{KBG04}
\citation{GLM12}
\citation{GMV06}
\citation{BFRSW00}
\citation{BS09}
\citation{MP78}
\citation{MRL99}
\citation{GK01}
\citation{BS09}
\citation{SBAS04}
\citation{CM04}
\citation{GKMS02}
\citation{ZW07}
\citation{CJP08,GM09}
\citation{WLYC13}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {I-A}}Applications}{2}{subsection.1.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {I-B}}Contributions}{2}{subsection.1.2}}
\@writefile{toc}{\contentsline {section}{\numberline {II}Related Work}{2}{section.2}}
\newlabel{sec:related}{{II}{2}{Related Work}{section.2}{}}
\citation{CCD12,D12,MPTW12}
\citation{knuth}
\@writefile{toc}{\contentsline {section}{\numberline {III}Preliminaries}{3}{section.3}}
\newlabel{sec:def}{{III}{3}{Preliminaries}{section.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {III-A}}Problem Definition}{3}{subsection.3.1}}
\newlabel{sec:probdef}{{\unhbox \voidb@x \hbox {III-A}}{3}{Problem Definition}{subsection.3.1}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces KS-statistic: the greatest difference between distribution functions}}{3}{figure.1}}
\newlabel{fig:KS}{{1}{3}{KS-statistic: the greatest difference between distribution functions}{figure.1}{}}
\citation{GK01}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {III-B}}Quantile Sketches}{4}{subsection.3.2}}
\newlabel{def:sketch}{{1}{4}{Quantile Sketches}{definition.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {IV}One-sample Test}{4}{section.4}}
\newlabel{sec:onesample}{{IV}{4}{One-sample Test}{section.4}{}}
\newlabel{obs:sketchvalues}{{1}{4}{One-sample Test}{observation.1}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces OneSample($Q$, $n$, $F$)}}{4}{algorithm.1}}
\newlabel{alg:one-sample}{{1}{4}{One-sample Test}{algorithm.1}{}}
\newlabel{obs:sketcherror}{{2}{4}{One-sample Test}{observation.2}{}}
\newlabel{thm:onesampleguarantee}{{1}{4}{One-sample Test}{lemma.1}{}}
\newlabel{eq:squeeze1}{{1}{4}{One-sample Test}{equation.4.1}{}}
\newlabel{eq:indexbound}{{2}{5}{One-sample Test}{equation.4.2}{}}
\newlabel{eq:onesamplebound}{{3}{5}{One-sample Test}{equation.4.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {IV-A}}Computational Analysis}{5}{subsection.4.1}}
\@writefile{toc}{\contentsline {section}{\numberline {V}Two-Sample Test}{5}{section.5}}
\newlabel{sec:twosample}{{V}{5}{Two-Sample Test}{section.5}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces TwoSample($Q_1$, $n$, $Q_2$, $m$)}}{5}{algorithm.2}}
\newlabel{alg:two-sample}{{2}{5}{Two-sample algorithm}{algorithm.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {V-A}}Two-sample algorithm}{5}{subsection.5.1}}
\newlabel{thm:twosampleguarantee}{{2}{5}{Two-sample algorithm}{lemma.2}{}}
\newlabel{eq:squeeze}{{4}{5}{Two-sample algorithm}{equation.5.4}{}}
\citation{BS09}
\newlabel{eq:realindexerror}{{5}{6}{Two-sample algorithm}{equation.5.5}{}}
\newlabel{eq:approxindexerror}{{6}{6}{Two-sample algorithm}{equation.5.6}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {V-B}}Computational Analysis}{6}{subsection.5.2}}
\@writefile{toc}{\contentsline {section}{\numberline {VI}Picking $\epsilon $}{6}{section.6}}
\newlabel{sec:pickingeps}{{VI}{6}{Picking $\epsilon $}{section.6}{}}
\citation{GK01}
\citation{WLYC13}
\citation{SBAS04}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Lower bound illustration}}{7}{figure.2}}
\newlabel{fig:lb}{{2}{7}{Lower bound illustration}{figure.2}{}}
\@writefile{toc}{\contentsline {section}{\numberline {VII}Lower Bound}{7}{section.7}}
\newlabel{sec:lowerbound}{{VII}{7}{Lower Bound}{section.7}{}}
\newlabel{thm:lowerbound}{{3}{7}{Lower Bound}{lemma.3}{}}
\@writefile{toc}{\contentsline {section}{\numberline {VIII}Experimental Evaluation}{7}{section.8}}
\newlabel{sec:evaluation}{{VIII}{7}{Experimental Evaluation}{section.8}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Varying one-sample data size ($n$), for data drawn from N$(0, 1)$ compared with N$(0.1, 1)$, using $1\%$ memory}}{8}{figure.4}}
\newlabel{fig:onesample-varysize}{{4}{8}{Varying one-sample data size ($n$), for data drawn from N$(0, 1)$ compared with N$(0.1, 1)$, using $1\%$ memory}{figure.4}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {VIII-A}}One Sample}{8}{subsection.8.1}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Varying mean of one-sample distribution (N$(x, 1)$) compared with N$(0, 1)$, using $n = 10000$ and $1\%$ memory}}{8}{figure.5}}
\newlabel{fig:onesample-varydistance}{{5}{8}{Varying mean of one-sample distribution (N$(x, 1)$) compared with N$(0, 1)$, using $n = 10000$ and $1\%$ memory}{figure.5}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {VIII-B}}Two Sample}{8}{subsection.8.2}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Varying memory ($n = 10000$) for one-sample data drawn from various distributions}}{9}{figure.3}}
\newlabel{fig:onesample-varymemory}{{3}{9}{Varying memory ($n = 10000$) for one-sample data drawn from various distributions}{figure.3}{}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {N$(0, 1)$ vs.\ N$(0.1, 1)$}}}{9}{figure.3}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {U$(0, 1)$ vs.\ U$(0.1, 1)$}}}{9}{figure.3}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {P$(1, 1)$ vs.\ P$(1.1, 1)$}}}{9}{figure.3}}
\newlabel{fig:varymem-normal}{{6(a)}{9}{Subfigure 6(a)}{subfigure.6.1}{}}
\newlabel{sub@fig:varymem-normal}{{(a)}{9}{Subfigure 6(a)\relax }{subfigure.6.1}{}}
\newlabel{fig:varymem-uniform}{{6(b)}{9}{Subfigure 6(b)}{subfigure.6.2}{}}
\newlabel{sub@fig:varymem-uniform}{{(b)}{9}{Subfigure 6(b)\relax }{subfigure.6.2}{}}
\newlabel{fig:varymem-pareto}{{6(c)}{9}{Subfigure 6(c)}{subfigure.6.3}{}}
\newlabel{sub@fig:varymem-pareto}{{(c)}{9}{Subfigure 6(c)\relax }{subfigure.6.3}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Varying memory ($n = m = 10000$) for two-sample data drawn from various distributions}}{9}{figure.6}}
\newlabel{fig:twosample-varymem}{{6}{9}{Varying memory ($n = m = 10000$) for two-sample data drawn from various distributions}{figure.6}{}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {N$(0, 1)$ vs.\ N$(0.1, 1)$}}}{9}{figure.6}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {U$(0, 1)$ vs.\ U$(0.1, 1)$}}}{9}{figure.6}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {P$(1, 1)$ vs.\ P$(1.1, 1)$}}}{9}{figure.6}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces Varying two-sample data size ($n = m$), for data drawn from N$(0, 1)$ and N$(0.1, 1)$, using $1\%$ memory}}{9}{figure.7}}
\newlabel{fig:twosample-varyboth}{{7}{9}{Varying two-sample data size ($n = m$), for data drawn from N$(0, 1)$ and N$(0.1, 1)$, using $1\%$ memory}{figure.7}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Varying data size of one sample ($m$) keeping other sample fixed ($n = 10000$) for data drawn from N$(0, 1)$ and N$(0.1, 1)$, using $1\%$ memory}}{9}{figure.8}}
\newlabel{fig:twosample-varyone}{{8}{9}{Varying data size of one sample ($m$) keeping other sample fixed ($n = 10000$) for data drawn from N$(0, 1)$ and N$(0.1, 1)$, using $1\%$ memory}{figure.8}{}}
\bibstyle{abbrv}
\bibdata{references}
\bibcite{BFRSW00}{1}
\bibcite{BS09}{2}
\bibcite{CJP08}{3}
\bibcite{CPB93}{4}
\bibcite{CCD12}{5}
\bibcite{CM04}{6}
\bibcite{D12}{7}
\bibcite{GKMS02}{8}
\bibcite{GLM12}{9}
\bibcite{GK01}{10}
\bibcite{GM09}{11}
\bibcite{GMV06}{12}
\bibcite{KMFB04}{13}
\bibcite{KBG04}{14}
\@writefile{lof}{\contentsline {figure}{\numberline {10}{\ignorespaces Varying memory for real two-sample data}}{10}{figure.10}}
\newlabel{fig:twosample-varymem-real}{{10}{10}{Varying memory for real two-sample data}{figure.10}{}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Astronomy data}}}{10}{figure.10}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Light data}}}{10}{figure.10}}
\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Inter-arrival data}}}{10}{figure.10}}
\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces Scatter plot of estimated vs.\ real values of KS-statistic ($n = m = 10000$) between two-sample data drawn from N$(0, 1)$ and various distributions of the form N$(x, 1)$, using $1\%$ memory. The $y = x$ line is also shown for reference.}}{10}{figure.9}}
\newlabel{fig:twosample-varydistance}{{9}{10}{Scatter plot of estimated vs.\ real values of KS-statistic ($n = m = 10000$) between two-sample data drawn from N$(0, 1)$ and various distributions of the form N$(x, 1)$, using $1\%$ memory. The $y = x$ line is also shown for reference}{figure.9}{}}
\@writefile{toc}{\contentsline {section}{\numberline {IX}Conclusions}{10}{section.9}}
\newlabel{sec:conclusions}{{IX}{10}{Conclusions}{section.9}{}}
\@writefile{toc}{\contentsline {section}{References}{10}{section*.1}}
\bibcite{knuth}{15}
\bibcite{KSXZ04}{16}
\bibcite{LSOXZ06}{17}
\bibcite{MFHH05}{18}
\bibcite{MRL99}{19}
\bibcite{MPTW12}{20}
\bibcite{MP78}{21}
\bibcite{CHANDRA}{22}
\bibcite{SKA}{23}
\bibcite{SBAS04}{24}
\bibcite{WJ03}{25}
\bibcite{WLYC13}{26}
\bibcite{ZW07}{27}
\@writefile{toc}{\contentsline {section}{Appendix}{11}{section*.2}}
\newlabel{app:extract}{{A}{11}{\appendixname }{section*.2}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {3}{\ignorespaces ExtractValues($Q$, $n$)}}{11}{algorithm.3}}
\newlabel{alg:extract}{{3}{11}{\appendixname }{algorithm.3}{}}
\newlabel{app:binsearch}{{A}{11}{\appendixname }{ALC@unique.24}{}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {4}{\ignorespaces ReverseQuantile($Q$, $n$, $x$)}}{11}{algorithm.4}}
\newlabel{alg:reverse-quantile}{{4}{11}{\appendixname }{algorithm.4}{}}
